package LeetCode;

import java.util.Arrays;
import java.util.LinkedList;

public class Solution3 {

    public static void main(String[] args) {
        String s = "a+b*c-d";
        String[] arr = turnToSuffix(s).split("");


        System.out.println(Arrays.toString(arr));
        //System.out.println(evalRPN(arr));
    }
    public static int evalRPN(String[] tokens) {
        LinkedList<Integer> stack = new LinkedList<>();
        for (int i = 0; i < tokens.length; i++) {
            int a = 0;
            int b = 0;
            switch (tokens[i]) {
                case "+":
                    b = stack.pop();
                    a = stack.pop();
                    stack.push(a + b);
                    break;
                case "-":
                    b = stack.pop();
                    a = stack.pop();
                    stack.push(a - b);
                    break;
                case "*":
                    b = stack.pop();
                    a = stack.pop();
                    stack.push(a * b);
                    break;
                case "/":
                    b = stack.pop();
                    a = stack.pop();
                    stack.push(a / b);
                    break;
                default:
                    stack.push(Integer.parseInt(tokens[i]));
                    break;
            }
        }

        return stack.pop();
    }

    //"3+2*1*2"
    //321*2*+
    //+*

    public static String turnToSuffix(String s) {
        LinkedList<Character> list = new LinkedList<>();
        StringBuilder newStr = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            char a = s.charAt(i);
            if (a == '+' || a == '-' || a == '*' || a == '/') {
                if (list.size() == 0) {
                    list.push(a);
                    continue;
                } else if ( (list.peek() == '+' || list.peek() == '-' || list.peek() == '*' || list.peek() == '/') && (a == '+' || a == '-') ) {
                    newStr.append(list.pop());

                } else if ( (list.peek() == '*' || list.peek() == '/' ) && (a == '*' || a == '/') ) {
                    newStr.append(list.pop());

                } else if ( ( list.peek() == '+'  || list.peek() == '-') && (a == '*' || a == '/') ) {
                    list.push(a);
                    continue;
                }

                while (list.size() != 0 ) {
                    if ((list.peek() == '+' || list.peek() == '-' || list.peek() == '*' || list.peek() == '/') && (a == '+' || a == '-')) {
                        newStr.append(list.pop());
                    } else if ((list.peek() == '*' || list.peek() == '/' ) && (a == '*' || a == '/')) {
                        newStr.append(list.pop());
                    }else {
                        break;
                    }
                }
                list.push(a);

            } else {
                newStr.append(a);
            }
        }

        int count = list.size();
        for (int i = 0; i < count; i++) {
            newStr.append(list.pop());
        }
        return newStr.toString();
    }
}
